package LearnAlgorithm.g_数学问题;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-17 19:58
 * @description: LeetcodeLearnAlgorithm -> LearnAlgorithm.g_数学问题
 */
/*
寻找素数中的等差数列
素数等差数列是等差数列的一种。在等差数列中，任何相邻两项的差相等。
该差值称为公差。类似“7、37、67、97、127、157”这样完全由素数组成的等差数列叫做素数等差数列。

蓝桥杯 04/08/2017
在小于10的素数中有3、5、7组成的等差数列，在小于30的素数中有11、17、23、29组成的等差数列。

试找出区间[100,1000]内的素数构成的最大等差数列（即等差数列包含的素数个数最多）并打印输出。
 */
public class l寻找素数中的等差数列 {

    public static void main(String[] args) {
        l寻找素数中的等差数列 test = new l寻找素数中的等差数列();
        List<Integer> list = new LinkedList<>();
        test.createPrimeList(100, 1000, list);
        /*for (Integer element : list) {
            System.out.println(element);
        }*/
        test.findList(list);
    }

    public void findList(List<Integer> list) {
        int resultListLength = 1;
        int currentListLength = 1;
        int resultListLastElement = 0;
        int resultListPublicErrand = 0;

        /*
        根据粗略数据估算
        [100,1000]内，最小的公差只能比30大，比900小，否则没意义了
         */
        //负责迭代公差，因为我们不知道什么公差是最优的，所以只能循环穷举
        for (int publicErrand = 30; publicErrand < 900; publicErrand++) {
            //定义起始元素，因为我们不知道起始元素最优从什么时候开始，只能穷举
            for (int start = 0; start < list.size(); start++) {
                int current = start;
                //逐个扫描current后面的素数，符合公差，那就加入并增加currentList的长度
                for (int next = current + 1; next < list.size(); next++) {
                    if (list.get(next) - list.get(current) < publicErrand) {
                        //在穷举next过程中，如果next-current<publicErrand；那么什么也不做，继续看后面的next即可
                    } else if (list.get(next) - list.get(current) > publicErrand) {
                        /*
                        next-current大于publicErrand，
                        因为list是递增的
                        那么后面的next就全部更加不符合了
                        所以不穷举了，直接中断这个start开始的list
                        同时判断这个list是不是最优list
                         */
                        if (currentListLength > resultListLength) {
                            resultListLength = currentListLength;
                            resultListLastElement = current;
                            resultListPublicErrand = publicErrand;
                        }
                        //为后面的穷举回溯
                        currentListLength = 0;
                        break;
                    } else {
                        //next-current == publicErrand
                        currentListLength++;
                        current = next;//更新current
                    }
                }
                /*
                next走尽了，跳出循环，的情况
                代表以start开始的list已经寻找完成
                此时判断这个list是不是最优list
                 */
                if (currentListLength > resultListLength) {
                    resultListLength = currentListLength;
                    resultListLastElement = current;
                    resultListPublicErrand = publicErrand;
                }
                //为后面的穷举回溯
                currentListLength = 0;
            }
        }

        /*
        跳出大循环，代表搜索结束
        输出最优解的各种参数
         */
        System.out.println("公差序列元素个数：" + resultListLength);
        System.out.println("序列的最后一个元素：" + list.get(resultListLastElement));
        System.out.println("最优公差是：" + resultListPublicErrand);
        /*
        完成题目要求打印list
         */
        for (int i = 0; i < resultListLength; i++) {
            System.out.println(list.get(resultListLastElement) - i * resultListPublicErrand);
        }
    }

    /**
     * 使用埃式筛法，求出范围内的所有素数
     *
     * @param from
     * @param to
     * @param list
     * @return
     */
    public void createPrimeList(int from, int to, List<Integer> list) {
        boolean[] arr = new boolean[to + 1];
        Arrays.fill(arr, true);
        //初始化数组；自然数0，1不是素数
        arr[0] = false;
        arr[1] = false;
        //初始化数组；所有偶数一定不是素数，除了2这个偶数
        for (int i = 4; i <= to; i += 2) {
            arr[i] = false;
        }
        //埃式筛法
        for (int i = 3; i < Math.sqrt(to); i++) {
            if (arr[i]) {
                for (int j = 2; j * i <= to; j++) {
                    arr[j * i] = false;
                }
            }
        }
        for (int i = from; i < to; i++) {
            if (arr[i]) {
                list.add(i);
            }
        }
    }
}
